namespace AdvancedTraining.Lesson42;

/// <summary>
/// 二叉搜索树中找到最接近目标值的K个节点
/// </summary>
/// <remarks>
/// https://www.cnblogs.com/fuxuemingzhu/p/15435876.html
/// LeetCode 272. Closest Binary Search Tree Value II
///
/// 问题描述：
/// 给定一个不为空的二叉搜索树（BST）和一个目标值 target，在 BST 中找到最接近 target 的 k 个值。
///
/// 算法思路：
/// 使用双栈方法来高效解决二叉搜索树中找到最接近目标值的K个节点的问题：
///
/// 1. 两个栈结构：
///    - moreTops：存储大于等于target的节点路径，用于快速找后继
///    - lessTops：存储小于等于target的节点路径，用于快速找前驱
///
/// 2. 核心方法：
///    - GetMoreTops()：在BST中找到≥target的最接近节点，构建后继栈
///    - GetLessTops()：在BST中找到≤target的最接近节点，构建前驱栈
///    - GetSuccessor()：获取后继节点并调整栈
///    - GetPredecessor()：获取前驱节点并调整栈
///
/// 3. 选择策略：
///    - 比较两个栈顶节点与target的距离
///    - 选择距离更小的节点，然后获取其前驱或后继
///
/// 时间复杂度：O(n + k log n)，其中n是树节点数，k是要找的节点数
/// 空间复杂度：O(log n)，主要用于存储栈
/// </remarks>
public class ClosestBinarySearchTreeValueIi //leetcode_0272
{
    /// <summary>
    /// 在二叉搜索树中找到最接近目标值的k个节点
    /// </summary>
    /// <param name="root">二叉搜索树根节点</param>
    /// <param name="target">目标值</param>
    /// <param name="k">需要找的节点数量</param>
    /// <returns>最接近target的k个节点值的列表</returns>
    public static List<int> ClosestKValues(TreeNode root, double target, int k)
    {
        var ret = new List<int>();
        // >=target，最近的节点，而且需要快速找后继的这么一种结构
        var moreTops = new Stack<TreeNode>();
        // <=target，最近的节点，而且需要快速找前驱的这么一种结构
        var lessTops = new Stack<TreeNode>();
        GetMoreTops(root, target, moreTops);
        GetLessTops(root, target, lessTops);
        if (moreTops.Count > 0 && lessTops.Count > 0 && moreTops.Peek().Val == lessTops.Peek().Val)
            GetPredecessor(lessTops);
        while (k-- > 0)
            if (moreTops.Count == 0)
            {
                ret.Add(GetPredecessor(lessTops));
            }
            else if (lessTops.Count == 0)
            {
                ret.Add(GetSuccessor(moreTops));
            }
            else
            {
                var diffs = Math.Abs(moreTops.Peek().Val - target);
                var diffP = Math.Abs(lessTops.Peek().Val - target);
                if (diffs < diffP)
                    ret.Add(GetSuccessor(moreTops));
                else
                    ret.Add(GetPredecessor(lessTops));
            }

        return ret;
    }

    /// <summary>
    /// 在root为头的树上找到>=target，且最接近target的节点
    /// 并且找的过程中，只要某个节点x往左走了，就把x放入moreTops里
    /// </summary>
    /// <param name="root">二叉搜索树根节点</param>
    /// <param name="target">目标值</param>
    /// <param name="moreTops">存储大于等于target的节点路径的栈</param>
    private static void GetMoreTops(TreeNode? root, double target, Stack<TreeNode> moreTops)
    {
        while (root != null)
            if (root.Val == target)
            {
                moreTops.Push(root);
                break;
            }
            else if (root.Val > target)
            {
                moreTops.Push(root);
                root = root.Left;
            }
            else
            {
                root = root.Right;
            }
    }

    /// <summary>
    /// 在root为头的树上找到<=target，且最接近target的节点
    /// 并且找的过程中，只要某个节点x往右走了，就把x放入lessTops里
    /// </summary>
    /// <param name="root">二叉搜索树根节点</param>
    /// <param name="target">目标值</param>
    /// <param name="lessTops">存储小于等于target的节点路径的栈</param>
    private static void GetLessTops(TreeNode root, double target, Stack<TreeNode> lessTops)
    {
        while (root != null)
            if (root.Val == target)
            {
                lessTops.Push(root);
                break;
            }
            else if (root.Val < target)
            {
                lessTops.Push(root);
                root = root.Right;
            }
            else
            {
                root = root.Left;
            }
    }

    /// <summary>
    /// 返回moreTops的头部的值，并且调整moreTops以便能很快找到返回节点的后继节点
    /// </summary>
    /// <param name="moreTops">存储大于等于target的节点路径的栈</param>
    /// <returns>后继节点的值</returns>
    private static int GetSuccessor(Stack<TreeNode> moreTops)
    {
        var cur = moreTops.Pop();
        var ret = cur.Val;
        cur = cur.Right;
        while (cur != null)
        {
            moreTops.Push(cur);
            cur = cur.Left;
        }

        return ret;
    }

    /// <summary>
    /// 返回lessTops的头部的值，并且调整lessTops以便能很快找到返回节点的前驱节点
    /// </summary>
    /// <param name="lessTops">存储小于等于target的节点路径的栈</param>
    /// <returns>前驱节点的值</returns>
    private static int GetPredecessor(Stack<TreeNode> lessTops)
    {
        var cur = lessTops.Pop();
        var ret = cur.Val;
        cur = cur.Left;
        while (cur != null)
        {
            lessTops.Push(cur);
            cur = cur.Right;
        }

        return ret;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== ClosestBinarySearchTreeValueIi 测试 ===");

        // 测试用例1：基本示例 - LeetCode官方示例
        var root1 = BuildBst(new int[] { 4, 2, 5, 1, 3 });
        Console.WriteLine("测试1 - 基本示例:");
        Console.WriteLine($"BST: [1,2,3,4,5], target: 3.714286, k: 2");
        var result1 = ClosestKValues(root1, 3.714286, 2);
        Console.WriteLine($"结果: [{string.Join(",", result1)}] (期望: [4,3] 或 [3,4])");
        Console.WriteLine();

        // 测试用例2：目标值小于所有节点
        var root2 = BuildBst(new int[] { 4, 2, 6, 1, 3, 5, 7 });
        Console.WriteLine("测试2 - 目标值小于所有节点:");
        Console.WriteLine($"BST: [1,2,3,4,5,6,7], target: 0.5, k: 3");
        var result2 = ClosestKValues(root2, 0.5, 3);
        Console.WriteLine($"结果: [{string.Join(",", result2)}] (期望: [1,2,3])");
        Console.WriteLine();

        // 测试用例3：目标值大于所有节点
        var root3 = BuildBst(new int[] { 4, 2, 6, 1, 3, 5, 7 });
        Console.WriteLine("测试3 - 目标值大于所有节点:");
        Console.WriteLine($"BST: [1,2,3,4,5,6,7], target: 7.8, k: 2");
        var result3 = ClosestKValues(root3, 7.8, 2);
        Console.WriteLine($"结果: [{string.Join(",", result3)}] (期望: [7,6])");
        Console.WriteLine();

        // 测试用例4：目标值等于某个节点
        var root4 = BuildBst(new int[] { 4, 2, 6, 1, 3, 5, 7 });
        Console.WriteLine("测试4 - 目标值等于某个节点:");
        Console.WriteLine($"BST: [1,2,3,4,5,6,7], target: 4.0, k: 3");
        var result4 = ClosestKValues(root4, 4.0, 3);
        Console.WriteLine($"结果: [{string.Join(",", result4)}] (期望: [4,3,5] 或类似组合)");
        Console.WriteLine();

        // 测试用例5：k值等于节点数
        var root5 = BuildBst(new int[] { 3, 1, 5 });
        Console.WriteLine("测试5 - k值等于节点数:");
        Console.WriteLine($"BST: [1,3,5], target: 3.2, k: 3");
        var result5 = ClosestKValues(root5, 3.2, 3);
        Console.WriteLine($"结果: [{string.Join(",", result5)}] (期望: [1,3,5] 的某种排列)");
        Console.WriteLine();

        // 测试用例6：单个节点
        var root6 = new TreeNode(10);
        Console.WriteLine("测试6 - 单个节点:");
        Console.WriteLine($"BST: [10], target: 8.5, k: 1");
        var result6 = ClosestKValues(root6, 8.5, 1);
        Console.WriteLine($"结果: [{string.Join(",", result6)}] (期望: [10])");
        Console.WriteLine();

        // 测试用例7：较大的BST
        var root7 = BuildBst(new int[] { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 });
        Console.WriteLine("测试7 - 较大的BST:");
        Console.WriteLine($"BST: [1,2,3,...,15], target: 9.3, k: 5");
        var result7 = ClosestKValues(root7, 9.3, 5);
        Console.WriteLine($"结果: [{string.Join(",", result7)}] (期望: 9附近的5个数字)");
        Console.WriteLine();

        // 测试用例8：目标值为小数，测试精度
        var root8 = BuildBst(new int[] { 10, 5, 15, 2, 7, 12, 18 });
        Console.WriteLine("测试8 - 目标值为小数:");
        Console.WriteLine($"BST: [2,5,7,10,12,15,18], target: 11.37, k: 4");
        var result8 = ClosestKValues(root8, 11.37, 4);
        Console.WriteLine($"结果: [{string.Join(",", result8)}] (期望: 11.37附近的4个数字)");
        Console.WriteLine();

        Console.WriteLine("=== 测试完成 ===");
        Console.WriteLine();
        Console.WriteLine("算法说明:");
        Console.WriteLine("- 使用双栈方法维护前后驱信息");
        Console.WriteLine("- moreTops栈：存储≥target的节点路径，用于找后继");
        Console.WriteLine("- lessTops栈：存储≤target的节点路径，用于找前驱");
        Console.WriteLine("- 每次比较栈顶节点与target的距离，选择更近的节点");
        Console.WriteLine("- 时间复杂度：O(n + k log n)，空间复杂度：O(log n)");
    }

    /// <summary>
    /// 根据数组构建二叉搜索树（用于测试）
    /// </summary>
    /// <param name="values">节点值数组</param>
    /// <returns>BST根节点</returns>
    private static TreeNode BuildBst(int[] values)
    {
        if (values == null || values.Length == 0)
            return null!;

        var root = new TreeNode(values[0]);
        for (var i = 1; i < values.Length; i++)
        {
            InsertIntoBst(root, values[i]);
        }
        return root;
    }

    /// <summary>
    /// 向BST中插入节点（用于测试）
    /// </summary>
    /// <param name="root">BST根节点</param>
    /// <param name="val">要插入的值</param>
    private static void InsertIntoBst(TreeNode root, int val)
    {
        var current = root;
        while (true)
        {
            if (val < current.Val)
            {
                if (current.Left == null)
                {
                    current.Left = new TreeNode(val);
                    break;
                }
                current = current.Left;
            }
            else
            {
                if (current.Right == null)
                {
                    current.Right = new TreeNode(val);
                    break;
                }
                current = current.Right;
            }
        }
    }

    public class TreeNode(int val)
    {
        public TreeNode? Left;
        public TreeNode? Right;
        public int Val = val;
    }
}